package 算法.leetcode.labuladong.structure;

import java.util.LinkedHashMap;

/**
 * @author lchenglong
 * @date 2022/6/22
 */
public class LRUCache {
    int cap;

    public LRUCache(int cap) {
        this.cap = cap;
    }

    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();
    public void put(int key,int val){
        // 如果key已经存在,修改val并设置为最近使用
        if (cache.containsKey(key)){
            cache.put(key,val);
            makeRecently(key);
        } else {
            if (cache.size()>=cap){
                deleteLeastRecently();
            }
            // 添加元素
            cache.put(key,val);
        }
    }

    public int get(int key){
        if (!cache.containsKey(key))return -1;
        // 设置为最近使用
        makeRecently(key);
        return cache.get(key);

    }

    // 将某个元素提升为最近使用
    public void makeRecently(int key){
        Integer val = cache.get(key);
        // 删除key,重新插入队尾
        cache.remove(key);
        cache.put(key,val);
    }

    public void deleteLeastRecently(){
        int needRemoveKey = cache.keySet().iterator().next();
        cache.remove(needRemoveKey);
    }

}
